#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <fstream>
#include <unordered_map>
#include <sstream>
#include <algorithm>
#include <string>
#include <math.h>
#include <cstring>

#include "mta.h"

using namespace mta;
using namespace std;

template<class Container>
void populateContainer(Container& items, istream& input){
	//assume stream is valid
	string s;
	while(getline(input, s)){
		string miss = s.substr(0, s.find_first_of('-'));
		list<string> corr;
		if(s.find(',')==s.npos){	//there is only one correction
			corr.push_back(s.substr(s.find_first_of('>')+1,s.size()));
		}
		else{				//there are many corrections
			s = s.substr(s.find_first_of('>')+1,s.size());	//now just corrections
			istringstream iss(s);
			string tk;
			while(getline(iss, tk, ',')){
				corr.push_back(tk);
			}
		}
		items.insert(items.end(), pair< string, list<string> >(miss, corr));
	}
}

// timer class
class timer {
public:
	timer() : start(clock()) {}
	double elapsed() { return ( clock() - start ) / CLOCKS_PER_SEC; }
	void reset() { start = clock(); }
private:
	double start;
};

class CompareString
{
public:
	bool operator()(const pair<string, list<string>>& left, const string& right)
	{
		return left.first < right;
	}
	bool operator()(const string& left, pair<string, const list<string>>& right)
	{
		return left < right.first;
	}
};

int main(){
	vector< pair<string, list<string> > > vwords;
	list< pair<string, list<string> > > lwords;
	map< string, list<string> > mwords;
	unordered_map< string, list<string> > uwords;

	//Read in the file 4 times
	ifstream ifs("misspelledwords.txt");
	if(!ifs){
		cerr << "you dun goofed" << endl;
		return(-1);
	}

	populateContainer(vwords, ifs);
	ifs.close();

	ifs.open("misspelledwords.txt");
	if(!ifs){
		cerr << "you dun goofed" << endl;
		return(-1);
	}

	populateContainer(lwords, ifs);
	ifs.close();

	ifs.open("misspelledwords.txt");
	if(!ifs){
		cerr << "you dun goofed" << endl;
		return(-1);
	}

	populateContainer(mwords, ifs);
	ifs.close();

	ifs.open("misspelledwords.txt");
	if(!ifs){
		cerr << "you dun goofed" << endl;
		return(-1);
	}

	populateContainer(uwords, ifs);
	ifs.close();
	
	//Q1
	timer t;
	for(pair<string, list<string>> p : vwords ){
		lower_bound(vwords.begin(), vwords.end(), p.first, CompareString());
	}
	cout << "Vector: " << t.elapsed()/vwords.size() << endl;

	t.reset();
	for(pair<string, list<string>> p : lwords ){
		lower_bound(lwords.begin(), lwords.end(), p.first, CompareString());
	}
	cout << "List: " << t.elapsed()/lwords.size() << endl;

	t.reset();
	for(pair<string, list<string>> p : mwords ){
		lower_bound(mwords.begin(), mwords.end(), p.first, CompareString());
	}
	cout << "Map: " << t.elapsed()/mwords.size() << endl;

	t.reset();
	for(pair<string, list<string>> p : uwords ){
		lower_bound(uwords.begin(), uwords.end(), p.first, CompareString());
	}
	cout << "unordered_map: " << t.elapsed()/uwords.size() << endl;
	

	MTAData m = MTAData("MTA_train_stop_data.txt", "transfers.txt");
	list<string> l = m.hereToThere("A41", "D04");
	for(string s : l)
		cout << m.getById(s) << endl;

}